package com.linchong.dynamicprogramming.medium;

import lombok.extern.slf4j.Slf4j;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-17 17:26
 * @Description: UniquePaths$62-不同路径-https://leetcode-cn.com/problems/unique-paths/
 */
@Slf4j
public class UniquePaths {

	/*
	 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
	 *
	 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
	 *
	 * 问总共有多少条不同的路径？
	 *
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/unique-paths
	 *
	 * 示例 1:
	 *
	 * 输入: m = 3, n = 2
	 * 输出: 3
	 * 解释:
	 * 从左上角开始，总共有 3 条路径可以到达右下角。
	 * 1. 向右 -> 向右 -> 向下
	 * 2. 向右 -> 向下 -> 向右
	 * 3. 向下 -> 向右 -> 向右
	 * 示例 2:
	 *
	 * 输入: m = 7, n = 3
	 * 输出: 28
	 *  
	 *
	 * 提示：
	 *
	 * 1 <= m, n <= 100
	 * 题目数据保证答案小于等于 2 * 10 ^ 9
	 *
	 *
	 */

	/**
	 * 所需步骤数
	 * @param m 行
	 * @param n 列
	 * @return steps
	 */
	public int uniquePaths(int m, int n) {

		int[][] router = new int[m][n];
		router[0][0] = 1;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if(i==0||j==0){
					router[i][j]=1;
					continue;
				}

				router[i][j] = router[i][j-1]+router[i-1][j];
			}
		}
		return router[m-1][n-1];
	}

	public static void main(String[] args) {
		int m = 7,n=3;
		UniquePaths instance = new UniquePaths();
		int step = instance.uniquePaths(m,n);
		log.info("the result is [{}]",step);

	}
}
